package leetCode;

/**
 * 14. 最长公共前缀
 *纵向扫描、横向扫描/停顿循环
 编写一个函数来查找字符串数组中的最长公共前缀。

 如果不存在公共前缀，返回空字符串""。

 示例 1：
 输入：strs = ["flower","flow","flight"]
 输出："fl"

 示例 2：
 输入：strs = ["dog","racecar","car"]
 输出：""
 解释：输入不存在公共前缀。

 提示：
 1 <= strs.length <= 200
 0 <= strs[i].length <= 200
 strs[i] 仅由小写英文字母组成
 */
public class LongestCommonPrefix {
    public static void main(String[] args) {
        String[] strs = new String[3];
        strs[0] = "flower";
        strs[1] = "flower";
        strs[2] = "flower";
        System.out.println(longestCommonPrefixMe(strs));
    }

    //暴力循环，问题点是会有各种数组越界风险，所以有很多判断
    //这是纵向扫描，还有横向扫描，遍历字符串为基础，69/27
    public static String longestCommonPrefixMe(String[] strs) {
        if ("".equals(strs[0])) {
            return "";
        } else if (strs.length == 1) {
            return strs[0];
        }
        StringBuilder sb = new StringBuilder();
        boolean flag = true;
        int j = 0;
        while (flag) {
            if (strs[0].length() == j) {
                flag = false;
                break;
            }
            char c = strs[0].charAt(j);
            for (int i =0;i< strs.length;i++) {
                if (strs[i].length() == j) {
                    flag = false;
                    break;
                } else if (c != strs[i].charAt(j)) {
                    flag = false;
                }
            }
            if (flag) {
                sb.append(c);
                j++;
            }
        }
        return sb.toString();
    }

    public static String longestCommonPrefix(String[] strs) {
        String s = strs[0];
        for (String str:strs) {
            while (!str.startsWith(s)) {
                if (s.length() == 0) return s;
                s = s.substring(0,s.length()-1);
            }
        }
        return s;
    }
}
